\chapter{Simulazione}
Con il termine {\bf simulazione} si intente lo studio di un modello matematico, semplificato, di un fenomeno utilizzando uno sistema di calcolo.\\
Alcune varianti sono: 
\begin{itemize}
\item Realtà virtuale
\item Progettazione dei sistemi (design, cad o model checking)
\item Studio di fenomeni complessi, caotici o pericolosi al fine di poter esegure predizioni sui comportamenti futuri del sistema.
\end{itemize}
Solitamente si ricorre all'uso di tecniche di simulazione quando i modelli assumono dei comportamenti caotici, ovvero delle piccole variazioni di stato provocano delle grande variazioni al sistema, quindi il modello matematico in questo caso risulta essere inutilizzabile. In tutti questi casi si usano delle tecniche di simulazione statistiche ed essendo in ambito statistico risulta essere molto importante l'interpretazione dei dati.\\
Essendo la simulazione di tipo statistica rispetta la legge dei grandi numeri, per cui per avere un modello attendibile il numero dei campioni preso in considerazione deve essere molto grande, tendente all'infinito.\\
La {\bf legge di Murphy} è in contraddizione con la legge dei grandi numeri, infatti questa afferma che se un evento di bassa probabilità si verifichera sicuramente, quindi questo ha degli effetti negativi nel caso di un modello con un ristretto numero di esperimenti.\\\\
Un modello deterministico consiste nel risolvere il modello matematico, non in una sua predizione. 
\section{Approccio statistico}
Per studiare le reti P2P e quelle sociali si utilizza un modello matematico di tipo statistico, si cerca quindi di classificare e riconoscere le diverse reti.
\subsection{Modelli statici e dinamici}
I modelli utilizzati per l'analisi sono modelli statici e dinamici.\\
Un modello statico non contiene il concetto di tempo, mentre in quelli dinamici il tempo è un concetto chiave al fine di poter studiare la variazione del modello in funzione nel tempo.
\section {Modelli Statici}
\subsection{Il Metodo Monte Carlo}
Il {\bf Metodo Monte Carlo} è statico e risulta computazionalmente più efficiente rispetto a quelli dinamici, per questo motivo il più delle volte si tende a semplificare un modello dinamico in un modello più semplice ma sopratutto statico, al fine di poter utilizzare il Metodo Monte Carlo.
\section{Modelli Dinamici}
Nei modelli dinamici si vuole studiare l'evoluzione nel tempo di una particolare caratteristica del sistema che si sta studiando.
\subsection{Modello Continuo}
In un modello dinamico continuo si effettua un campionamento per poter poi utilizzare modelli discreti in cui oppure è possibile risolvere il modello attraverso l'uso del calcolo numerico.\\\\
Nella {\bf Simulazione ad Eventi Discreti} si identificano quei momenti in cui si ha un cambio di stato, quindi ogni coppia(tempo, stato)identifica un evento che ha causato il cambio di stato. Questa soluzione risulta essere più efficiente in termini di costo piuttosto che memorizzare lo stato del sistema in ogni instante.
\section{Componenti fondamentali di un simulatore}
Le componenti fondamentali per effettuare delle simulazioni statistiche sono:
\begin{itemize}
\item Un modello da studiare
\item Un generatore di numeri casuali
\item Un motore di simulazione
\item L'analisi statistica dei risultati
\end{itemize}
\begin{center}
\begin{tabular}{ | r | c | c |}
\hline
Componenti & MonteCarlo & Discrete-Event \\ \hline
Modello & v & v \\ \hline
Generatore Random & v & v \\ \hline
Engine &  & v \\ \hline
Analisi Statisica & v & v \\ \hline
\end{tabular}
\end{center}
\subsection{Il Modello}
\subsection{Il Generatore Random}
Il generatore random è fondamentale sia nel caso del Modello Monte Carlo che nel Discrete-Event e deve generare sequenze di numeri casuali statisticamente indipendenti e identifcamente distribuiti.\\\\
Nel caso di una simulazione con il termine casuale si intende la generazione di un numero non predicibile e non riproducibile, quest'ultimo aspetto non è altrettanto vero in ambito informatico, in questo caso di definisce un generatore pseudo-random in modo tale da poter avere un comportamento statistico simile a quello desiderato, mantenendo però la riproducibilità degli esperimenti. Un generatore dato un \emph{seme}, generato in modo completamente casuale ha poi un comportamento deterministico nel generare la sequenza di numeri pseudo-casuali.\\\\
Inoltre il Generatore Random deve produrre distribuzioni pseudo casuali\\...\\\\
La soluzione migliore, dal punto di vista statistico, per generare un numero pseudo-casuale dato un seme consiste nell'utilizzare una funzione di {\bf hash crittografica}, anche se non efficiente dal punto di vista computazionale.\\
Un'ulteriore tecnica, che al contrario della funzione di hash, risulta essere computazionale vantaggiosa è la tecnica {\bf Congruente moltiplicativo} in cui il numero pseuso-random viene calcolato a partire dal numero precedente, la formula per calcolarlo è $x_{i+1}= Ax_i mod_B$, con A e B due costanti che devono essere scelte però in modo adeguato. Il numero massimo di numeri rappresentabili in questo caso risulta essere B-1, la funzione è periodica e lo 0 è escluso.
\doppioCapo
Ci sono varie tecniche per ottenere un generatore random, in seguito ne sono presentate 3
\paragraph{Tecnica di composizione}
Ho una distribuzione uniforme $r_1$ tale che $0\le r_1\le 1$, la sommo ad un'altra distribuzione $r_2, 0\le r_2 \le 1$, in questo modo ottengo una distribuzione con supporto compreso tra 0 e 2 con la seguente forma.\\ %immagine
Se sommo 3 distribuzioni otterrò una parabola e così via, in quanto la somma di variabili casuali equidistribuite è uguale al prodotto di convoluzione delle loro distribuzioni, quindi una distribuzione a supporto finito. Questa distribuzione per un numero di variabili $n \rightarrow \infty$ assomiglia sempre di più ad una gaussiana.\\
Questa tecnica è molto semplice come concetto ma per ottenere un singolo numero devo generarne n casuali.
\paragraph{Tecnica di rejezione}
Si parte da una curva C che rappresenta una distribuzione a supporto finito di qualsiasi forma, genero due variabili casuali $r_1, \left[0...m\right]$ e $r_2, \left[0...k\right]$, e in base ai valori che ottengo individuo un punto P sul piano di coordinate $\left( r_1, r_2\right)$. Se P si trova sotto la curva C uro $r_1$ come istanza di variabile casuale, altrimenti se sta sopra butto via $r_1$ ed $r_2$ e ne genero altre due finchè non trovo un punto P che stia sotto C.\\
Questa tecnica funziona bene se $r_1$ assomiglia ad una distribuzione uniforme, cioè se l'area sotto la curva C tende a quella del rettangolo mk, perchè in questo modo bastano pochi tentativi per trovare un buon $r_1$. Se invece l'area sotto la curva è piccola posso dover fare molti tentativi prima di trovare dei valori che vadano bene.\\
Un vantaggio della tecnica di rejezione è il fatto che non serva per forza una distribuzione analitica, ne va bene anche una empirica, ma deve comunque dipendere dalla distribuzione.
\paragraph{Metodo della funzione inversa}
Questo metodo ragiona sulla distribuzione cumulativa, che quindi è a supporto infinito, invece che sulla distribuzione di probabilità. Una distribuzione cumulativa può essere strettamente monotona, quindi invertibile, oppure non strettamente monotona, e di conseguenza non invertibile.\\
Supponiamo per semplicità che sia invertibile, dobbiamo generare un valore casuale di x basandoci sulla distribuzione in figura. Non ne siamo capaci in quanto possiamo generare solo un valore uniforme nell'intervallo $\left[ 0, 1\right]$. Questo intervallo corrisponde al codominio della funzione di distribuzione cumulativa, quindi basta definire sul codominio di x una funzione f e trovare x applicando l'inversa di f: in questo modo si riduce tutto alla complessità del calcolo di una funzione inversa. Come funzione si considera l'esponenziale negativa $f(x)=1-e^{-\lambda x}$, per trovare l'inversa basta fare il logaritmo.

\subsection{Il Motore}
Il {\bf motore di simulazione} viene usato solo per simulazioni ad eventi discreti in quanto contiene l'idea di funzione dipendente dal tempo che non è compresa nel metodo Monte Carlo. Si fa riferimento allo stato del sistema e alla rappresentazione eventi che modificano lo stato, in altre parole si vuole ottenre un diagramma che mi dica come cambia lo stato in funzione dei vari eventi che si verificano, il tempo è considerato come una variabile indipendente crescente.\\
Ho un insieme di eventi schedulati, che può cambiare a seguito di un cambiamento di stato: infatti potrei perdere degli eventi che avevo in programma o aqcuisirne di nuovi. Per questo per mantenere il motore serve una struttura che permetta di estrarre il primo elemento e le operazioni di inserimento e cancellazione in tempo ottimale. La struttura che meglio di tutte permette operazioni di questo tipo è la {\bf Coda con priorità} realizzata mediante heap, che permette di estrarre il primo elemento in tempo costante e le altre due operazioni in tempo logaritmico.
\subsection{L'analisi statistica}
I risultati di una simulazione dipendono sia dall'evoluzione degli stati nel tempo prodotta dal motore che da cosa effettivamente si sta chiedendo al simulatore, la domanda che si fa più di frequente è il cosa succede a partire da una stato iniziale dopo un certo tempo predefinito.\\
Spesso capita di ripetere le prove per un numero di volte k, ottenendo ogni volta risultati diversi $r_1,r_2,...,r_k$. Posso considerare il valor medio dei risultati ottenuto con $R=\frac{1}{k}\sum_{i=1}^k r_i$, ovviamente il risultato sarà più accurato al crescere di k. Per l'analisi dei risultati sfrutto l'idea di {\bf intervallo di confidenza}, cioè la probabilità di fare un errore considerando come media un certo valore, e il {\bf teorema del limite centrale}, che dice che aumentando il numero di istanze la distribuzione di probabilità tende ad una gaussiana.\\
Per lo studio di una gaussiana basta considerare due parametri, cioè il valor medio e la varianza. Quest'ultima può essere ottenuta come $\frac{1}{k}\sum_{i=1}^k (r_i-R)^2$, se non conosco il valore esatto di R come nel caso in questione si usa la sua stima. In questo modo però userei gli stessi campioni per media e varianza ottenendo informazioni minori. Il numero di valori indipendenti che posso avere è $k-1$, quindi divido per $k-1$ invece che per k.\\
Scelgo un $k'$ iniziale abbastanza grande da permettere di usare la gaussiana ma non troppo grande, empiricamente è stato stimato che un buon valore per iniziale è maggiore o uguale a 30. Il valor medio è la media $\pm$ la dimensione dell'intervallo di confidenza, se voglio un risultato più preciso aumento k e ripeto la simulazione: questo mi porterà ad avere una gaussiana più stretta e una varianza minore a parità di confidenza.\\
Il calcolo può essere parallelizzato su più macchine in quanto i risultati sono indipendenti tra loro.
\paragraph{Tecnica di tipo rigenerativo naturale}
L'applicabilità di questa tecnica dipende dal modella che sto simulando, devo sapere che tornerò più volte nello stato iniziale $S_0$ e che lo stato in cui mi trovo in un dato momento non dipende dagli stati in cui mi trovavo nei momenti precedenti, in questo modo si verifica l'assenza di memoria tipica dei sistemi markoviani.\\
Una simulazione di tipo rigenerativo naturale quindi termina quando ritorno nello stato iniziale, e può essere ripetuta semplicemente partendo dall'istanza di $S_0$ appena trovata invece che ripartire da capo grazie all'assenza di memoria. Per questo devo scegliere uno stato iniziale che saprò già essere frequente e i risultati non dipenderanno dalle mie scelte ma solo dal modello considerato, al contrario di quanto avveniva con le semplici prove ripetute in cui fissavo le condizioni in base a cui ottenevo i risultati.
